#include<string>
using namespace std;
class KMP {
private:
	void getNext(int* next, const string& p) {
		next[0] = -1;
		int i = 0, k = -1;
		while (i < p.size()-1) {
			if (k==-1||p[i] == p[k]) 
				next[++i] = ++k;
			else 
				k = next[k];
		}
	}

public:

	int find(const string& t, const string& p) {
		if (p.size() < 1) return 0;
		int* next = new int[p.size()];
		getNext(next, p);
		int i = 0, j = 0;
		int tlen = t.length(), plen = p.length();
		while (i < tlen &&j< plen) {
			if (j==-1||p[j] == t[i]) {
				++i;
				++j;
			}
			else {
				j = next[j];
			}
		}
		delete[] next;
		return j == p.size() ? i - p.size() : -1;
	}
};

int main() {
	string str = "Hello";
	string pattern = "ll";
	KMP kmp;
	kmp.find(str, pattern);

}